#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

using namespace std;


class Solution {
public:

    // 30. 串联所有单词的子串
    // https://leetcode.cn/problems/substring-with-concatenation-of-all-words/
    vector<int> findSubstring(string s, vector<string>& words) {
        if (words.empty())
        {
            return {};
        }
        int word_size = words[0].size();
        int len = word_size*words.size();
        if (len > s.size())
        {
            return {};
        }

        unordered_map<string, int> wordhash;
        vector<int> ans;

        for (auto& word : words)
        {
            ++wordhash[word];
        }

        for (int i = 0; i<word_size; ++i)
        {
            int left = i, right = i;
            int cnt = 0;
            unordered_map<string, int> shash;
            while (right < s.size())
            {
                string inword = s.substr(right, word_size);
                ++shash[inword];
                if (wordhash.count(inword) && shash[inword] <= wordhash[inword])
                    ++cnt;
                if (right - left + word_size > len)
                {
                    string out = s.substr(left, word_size);
                    if (wordhash.count(out) && shash[out] <= wordhash[out])
                        --cnt;
                    --shash[out];
                    left += word_size;
                }
                if (cnt == words.size())
                    ans.push_back(left);
                right += word_size;
            }
        }
        return ans;
    }

    // 76. 最小覆盖子串
    // https://leetcode.cn/problems/minimum-window-substring/
    string minWindow(string s, string t) {
        int thash[128] = { 0 };
        int shash[128] = { 0 };
        int left = 0, right = 0;
        int cnt = 0;
        int kinds = 0;

        int minlenth = INT_MAX;
        int begin = -1;

        for (auto ch : t)
            if (thash[ch]++ == 0) ++kinds;

        while (right < s.size())
        {
            char in = s[right];
            ++shash[in];
            if (shash[in] == thash[in])
                ++cnt;
            
            while (cnt == kinds)
            {
                if (right - left + 1 < minlenth)
                {
                    minlenth = right - left + 1;
                    begin = left;
                }
                // 出窗口
                char out = s[left++];
                if (shash[out] == thash[out])
                    --cnt;
                --shash[out];
            }
            ++right;
        }
        if (begin == -1) return "";
        else return s.substr(begin, minlenth);
    }
};